#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/8/14 14:10
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 后缀树.py
# @Software: PyCharm


class Trie:
    class Node:
        def __init__(self):
            self.end = False
            self.children = [None for i in range(27)]

    @staticmethod
    def ord(c):
        if ord('a') <= ord(c) <= ord('z'):
            return ord(c) - ord('a')
        elif ord('A') <= ord(c) <= ord('Z'):
            return ord(c) - ord('A')
        elif c == '$':
            return 26
        else:
            return -1

    @staticmethod
    def chr(i):
        if i < 26:
            return chr(ord('a') + i)
        else:
            return '$'

    def __init__(self):
        self.head = self.Node()

    def add(self, s):
        p = self.head
        ms = ''
        for c in s:
            ci = self.ord(c)
            if ci < 0:
                return ms
            if p and p.children[ci]:
                p = p.children[ci]
                ms += c
            else:
                p.children[ci] = self.Node()
                p = p.children[ci]
        p.end = True
        return ms

    def has(self, s):
        p = self.head
        for c in s:
            ci = self.ord(c)
            if ci < 0:
                return False
            if p and p.children[ci]:
                p = p.children[ci]
            else:
                return False
        return p.end

    def out(self):
        def work(head, s):
            if head.end:
                print(s)
            for i in range(27):
                if head.children[i]:
                    work(head.children[i], s + self.chr(i))
        work(self.head, '')


class SuffixTree:
    def __init__(self, s):
        s = s + '$' + s[::-1]
        self.tree = Trie()
        ans = ''
        for i in range(len(s)):
            ms = self.tree.add(s[i:])
            ans = ms if len(ms) > len(ans) else ans
        self.ans = ans

    def out(self):
        self.tree.out()


def main():
    trie = Trie()
    trie.add('ydy')
    trie.add('kid')
    print(trie.has('ydy'))
    print(trie.has('ctt'))
    print(trie.has('yd'))

    # st = SuffixTree('ydykid')
    # print(st.has('kid'))
    # print(st.has('ydy'))
    # print(st.has('dykid'))
    # print(st.has('ykid'))
    # print(st.has('kid'))
    # print(st.has('id'))
    # print(st.has('d'))
    # print(st.has('ydykid'))
    # print(st.has('yd'))

    s = 'babad'
    print(s, ':')
    st1 = SuffixTree(s)
    st1.out()
    print(st1.ans)
    s = "aacdefcaa"
    ss = s + '$' + s[::-1]
    print(s, ':', ss)
    st2 = SuffixTree(s)
    st2.out()
    print(st2.ans)
    print('ans: aa')
    print(chr(ord('a') + 26))


if __name__ == '__main__':
    main()
